home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / malloc.c < prev    next >
C/C++ Source or Header  |  1990-07-09  |  35KB  |  1,287 lines

  1. /* 
  2. Copyright (C) 1989 Free Software Foundation
  3.     written by Doug Lea (dl@oswego.edu)
  4.  
  5. This file is part of GNU CC.
  6.  
  7. GNU CC is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY.  No author or distributor
  9. accepts responsibility to anyone for the consequences of using it
  10. or for whether it serves any particular purpose or works at all,
  11. unless he says so in writing.  Refer to the GNU CC General Public
  12. License for full details.
  13.  
  14. Everyone is granted permission to copy, modify and redistribute
  15. GNU CC, but only under the conditions described in the
  16. GNU CC General Public License.   A copy of this license is
  17. supposed to have been given to you along with GNU CC so you
  18. can know your rights and responsibilities.  It should be in a
  19. file named COPYING.  Among other things, the copyright notice
  20. and this notice must be preserved on all copies.  
  21. */
  22.  
  23.  
  24.  
  25. #ifndef NO_LIBGXX_MALLOC   /* ignore whole file otherwise */
  26.  
  27. /* compile with -DMALLOC_STATS to collect statistics */
  28. /* collecting statistics slows down malloc by at least 15% */
  29.  
  30. #ifdef MALLOC_STATS
  31. #define UPDATE_STATS(ARGS) {ARGS;}
  32. #else
  33. #define UPDATE_STATS(ARGS)
  34. #endif
  35.  
  36. /* History
  37.  
  38.  
  39.    Tue Jan 16 04:54:27 1990  Doug Lea  (dl at g.oswego.edu)
  40.  
  41.      version 1 released in libg++
  42.  
  43.    Sun Jan 21 05:52:47 1990  Doug Lea  (dl at g.oswego.edu)
  44.  
  45.      bins are now own struct for, sanity.
  46.  
  47.      new victim search strategy: scan up and consolidate.
  48.      Both faster and less fragmentation.
  49.  
  50.      refined when to scan bins for consolidation, via consollink, etc.
  51.  
  52.      realloc: always try to expand chunk, avoiding some fragmentation.
  53.  
  54.      changed a few inlines into macros
  55.  
  56.      hardwired SBRK_UNIT to 4096 for uniformity across systems
  57.  
  58.    Tue Mar 20 14:18:23 1990  Doug Lea  (dl at g.oswego.edu)
  59.  
  60.      calloc and cfree now correctly parameterized.
  61.  
  62.    Sun Apr  1 10:00:48 1990  Doug Lea  (dl at g.oswego.edu)
  63.  
  64.      added memalign and valloc.
  65.  
  66. */
  67.  
  68. /* 
  69.   A version of malloc/free/realloc tuned for C++ applications.
  70.  
  71.   Here's what you probably want to know first:
  72.  
  73.   In various tests, this appears to be about as fast as,
  74.   and usually substantially less memory-wasteful than BSD/GNUemacs malloc.
  75.  
  76.   Generally, it is slower (by perhaps 20%) than bsd-style malloc
  77.   only when bsd malloc would waste a great deal of space in 
  78.   fragmented blocks, which this malloc recovers; or when, by
  79.   chance or design, nearly all requests are near the bsd malloc
  80.   power-of-2 allocation bin boundaries, and as many chunks are
  81.   used as are allocated. 
  82.  
  83.   It uses more space than bsd malloc only when, again by chance
  84.   or design, only bsdmalloc bin-sized requests are malloced, or when
  85.   little dynamic space is malloced, since this malloc may grab larger
  86.   chunks from the system at a time than bsd.
  87.  
  88.   In other words, this malloc seems generally superior to bsd
  89.   except perhaps for programs that are specially tuned to
  90.   deal with bsdmalloc's characteristics. But even here, the
  91.   performance differences are slight.
  92.  
  93.  
  94.   This malloc, like any other, is a compromised design. 
  95.  
  96.  
  97.   Chunks of memory are maintained using a `boundary tag' method as
  98.   described in e.g., Knuth or Standish.  This means that the size of
  99.   the chunk is stored both in the front of the chunk and at the end.
  100.   This makes consolidating fragmented chunks into bigger chunks very fast.
  101.   The size field is also used to hold bits representing whether a
  102.   chunk is free or in use.
  103.  
  104.   Malloced chunks have space overhead of 8 bytes: The preceding
  105.   and trailing size fields. When they are freed, the list pointer
  106.   fields are also needed.
  107.  
  108.   Available chunks are kept in doubly linked lists. The lists are
  109.   maintained in an array of bins using a power-of-two method, except
  110.   that instead of 32 bins (one for each 1 << i), there are 128: each
  111.   power of two is split in quarters. The use of very fine bin sizes 
  112.   closely approximates the use of one bin per actually used size,
  113.   without necessitating the overhead of locating such bins. It is
  114.   especially desirable in common C++ applications where large numbers
  115.   of identically-sized blocks are malloced/freed in some dynamic
  116.   manner, and then later are all freed. The finer bin sizes make
  117.   finding blocks fast, with little wasted overallocation. The
  118.   consolidation methods ensure that once the collection of blocks is
  119.   no longer useful, fragments are gathered into bigger chunks awaiting new
  120.   roles.
  121.  
  122.   The bins av[i] serve as heads of the lists. Bins contain a dummy
  123.   header for the chunk lists, and a `dirty' field used to indicate
  124.   whether the list may need to be scanned for consolidation.
  125.  
  126.   On allocation, the bin corresponding to the request size is
  127.   scanned, and if there is a chunk with size >= requested, it
  128.   is split, if too big, and used.
  129.  
  130.   If no chunk exists in the list, a bigger chunk is found. To minimize 
  131.   unsuccessful scanning of a large number of probably empty bins
  132.   (as happens when so many bins are used), a single designated
  133.   ``victim'' ibin s maintained, and is considered first. The designated
  134.   victim is that holding the last remaindered or consolidated chunk.
  135.   If the victim is unusable (too small), then a new victim is
  136.   searched for by scanning bigger bins. 
  137.  
  138.   If the victim is usable, it is split. The remainder is placed on
  139.   the back of the appropriate bin list. (All freed chunks are placed
  140.   on fronts of lists. All remaindered or consolidated chunks are
  141.   placed on the rear. Correspondingly, searching within a bin
  142.   starts at the front, but finding victims is from the back. All
  143.   of this approximates  the  effect of having 2 kinds of lists per 
  144.   bin: returned chunks vs unallocated chunks, but without the overhead 
  145.   of maintaining 2 lists.)
  146.  
  147.   If no victim can be found, then smaller bins are examined for
  148.   consolidation.
  149.  
  150.   Finally, if consolidation fails to come up with a usable chunk,
  151.   more space is obtained from the system.
  152.  
  153.   Deallocation (free) consists only of placing the chunk on
  154.   a list.
  155.  
  156.   Reallocation proceeds in the usual way. If a chunk can be extended,
  157.   it is, else a malloc-copy-free sequence is taken.
  158.  
  159.   memalign requests more than enough space from malloc, finds a
  160.   spot within that chunk that meets the alignment request, and
  161.   then possibly frees the leading and trailing space. Overreliance
  162.   on memalign is a sure way to fragment space.
  163.  
  164.  
  165.   Some other implementation matters:
  166.  
  167.   8 byte alignment is currently hardwired into the design. Calling
  168.   memalign will return a chunk that is both 8-byte aligned, and
  169.   meets the requested alignment.
  170.  
  171.   The basic overhead of a used chunk is 8 bytes: 4 at the front and
  172.   4 at the end.
  173.  
  174.   When a chunk is free, 8 additional bytes are needed for free list
  175.   pointers. Thus, the minimum allocatable size is 16 bytes.
  176.  
  177.   The existence of front and back overhead permits some reasonably
  178.   effective fence-bashing checks: The front and back fields must
  179.   be identical. This is checked only within free() and realloc().
  180.   The checks are fast enough to be made non-optional.
  181.  
  182.   The overwriting of parts of freed memory with the freelist pointers
  183.   can also be very effective (albeit in an annoying way) in helping 
  184.   users track down dangling pointers.
  185.  
  186.   User overwriting of freed space will often result in crashes
  187.   within malloc or free.
  188.   
  189.   These routines are also tuned to C++ in that free(0) is a noop and
  190.   a failed malloc automatically calls (*new_handler)(). 
  191.  
  192.   malloc(0) returns a pointer to something of the minimum allocatable size.
  193.  
  194.   Additional memory is gathered from the system (via sbrk) in a
  195.   way that allows chunks obtained across different sbrk calls to
  196.   be consolidated, but does not require contiguous memory: Thus,
  197.   it should be safe to intersperse mallocs with other sbrk calls.
  198.  
  199.   This malloc is NOT designed to work in multiprocessing applications.
  200.   No semaphores or other concurrency control are provided to ensure
  201.   that multiple malloc or free calls don't run at the same time,
  202.   which could be disasterous.
  203.  
  204.   VERY heavy use of inlines is made, for clarity. If this malloc
  205.   is ported via a compiler without inlining capabilities, all
  206.   inlines should be transformed into macros -- making them non-inline
  207.   makes malloc at least twice as slow.
  208.  
  209.  
  210. */
  211.  
  212.  
  213. /* preliminaries */
  214.  
  215. #ifdef __cplusplus
  216. #include <stdio.h>
  217. #else
  218. #include "//usr/include/stdio.h"  /* needed for error reporting */
  219. #endif
  220.  
  221. #ifdef __cplusplus
  222. extern "C" {
  223. #endif
  224.  
  225. #ifdef USG
  226. extern void*     memset(void*, int, int);
  227. extern void*     memcpy(void*,  const void*, int);
  228. inline void      bzero(void* s, int l) { memset(s, 0, l); }
  229. inline void      bcopy(const void* s, void* d, int l) { memcpy(d, s, l); }
  230. #else
  231. extern void      bcopy(void*, void*, unsigned int);
  232. extern void      bzero(void*, unsigned int);
  233. #endif
  234.  
  235. extern void*     sbrk(unsigned int);
  236.  
  237. #ifndef __cplusplus
  238. #ifndef USG
  239. extern int       fputs(const char*, FILE*);
  240. extern int       fprintf(FILE*, const char*, ...);
  241. #endif
  242. #endif
  243.  
  244. #ifdef __GNUC__
  245. extern volatile void abort();
  246. #else
  247. extern void abort();
  248. #endif
  249.  
  250. #ifdef __cplusplus
  251. };  /* end of extern "C" */
  252. #endif
  253.  
  254.  
  255. /* A good multiple to call sbrk with */
  256.  
  257. #define SBRK_UNIT 4096 
  258.  
  259.  
  260.  
  261. /* how to die on detected error */
  262.  
  263. #ifdef __GNUC__
  264. static volatile void malloc_user_error()
  265. #else
  266. static void malloc_user_error()
  267. #endif
  268. {
  269.   fputs("malloc/free/realloc: clobbered space detected\n", stderr); abort();
  270. }
  271.  
  272.  
  273.  
  274. /*  Basic overhead for each malloc'ed chunk */
  275.  
  276.  
  277. struct malloc_chunk
  278. {
  279.   unsigned int         size;     /* Size in bytes, including overhead. */
  280.                                  /* Or'ed with INUSE if in use. */
  281.  
  282.   struct malloc_chunk* fd;       /* double links -- used only if free. */
  283.   struct malloc_chunk* bk;
  284.  
  285. };
  286.  
  287. typedef struct malloc_chunk* mchunkptr;
  288.  
  289. struct malloc_bin
  290. {
  291.   struct malloc_chunk hd;        /* dummy list header */
  292.   unsigned int        dirty;     /* True if maybe consolidatable */
  293.                                  /* Wasting a word here makes */
  294.                                  /* sizeof(bin) a power of 2, */
  295.                                  /* which makes size2bin() faster */
  296. };
  297.  
  298. typedef struct malloc_bin* mbinptr;
  299.  
  300.  
  301. /*  sizes, alignments */
  302.  
  303.  
  304. #define SIZE_SZ                   (sizeof(unsigned int))
  305. #define MALLOC_MIN_OVERHEAD       (SIZE_SZ + SIZE_SZ)
  306. #define MALLOC_ALIGN_MASK         (MALLOC_MIN_OVERHEAD - 1)
  307.  
  308. #define MINSIZE (sizeof(struct malloc_chunk) + SIZE_SZ) /* MUST == 16! */
  309.  
  310.  
  311. /* pad request bytes into a usable size */
  312.  
  313. static inline unsigned int request2size(unsigned int request)
  314. {
  315.   return  (request == 0) ?  MINSIZE : 
  316.     ((request + MALLOC_MIN_OVERHEAD + MALLOC_ALIGN_MASK) 
  317.       & ~(MALLOC_ALIGN_MASK));
  318. }
  319.  
  320.  
  321. static inline int aligned_OK(void* m)  
  322. {
  323.   return ((unsigned int)(m) & (MALLOC_ALIGN_MASK)) == 0;
  324. }
  325.  
  326.  
  327. /* size field or'd with INUSE when in use */
  328. #define INUSE  0x1
  329.  
  330.  
  331.  
  332. /* the bins, initialized to have null double linked lists */
  333.  
  334. #define MAXBIN 120   /* 1 more than needed for 32 bit addresses */
  335.  
  336. #define FIRSTBIN (&(av[0])) 
  337.  
  338. static struct malloc_bin  av[MAXBIN] = 
  339. {
  340.   { { 0, &(av[0].hd),  &(av[0].hd) }, 0 },
  341.   { { 0, &(av[1].hd),  &(av[1].hd) }, 0 },
  342.   { { 0, &(av[2].hd),  &(av[2].hd) }, 0 },
  343.   { { 0, &(av[3].hd),  &(av[3].hd) }, 0 },
  344.   { { 0, &(av[4].hd),  &(av[4].hd) }, 0 },
  345.   { { 0, &(av[5].hd),  &(av[5].hd) }, 0 },
  346.   { { 0, &(av[6].hd),  &(av[6].hd) }, 0 },
  347.   { { 0, &(av[7].hd),  &(av[7].hd) }, 0 },
  348.   { { 0, &(av[8].hd),  &(av[8].hd) }, 0 },
  349.   { { 0, &(av[9].hd),  &(av[9].hd) }, 0 },
  350.  
  351.   { { 0, &(av[10].hd), &(av[10].hd) }, 0 },
  352.   { { 0, &(av[11].hd), &(av[11].hd) }, 0 },
  353.   { { 0, &(av[12].hd), &(av[12].hd) }, 0 },
  354.   { { 0, &(av[13].hd), &(av[13].hd) }, 0 },
  355.   { { 0, &(av[14].hd), &(av[14].hd) }, 0 },
  356.   { { 0, &(av[15].hd), &(av[15].hd) }, 0 },
  357.   { { 0, &(av[16].hd), &(av[16].hd) }, 0 },
  358.   { { 0, &(av[17].hd), &(av[17].hd) }, 0 },
  359.   { { 0, &(av[18].hd), &(av[18].hd) }, 0 },
  360.   { { 0, &(av[19].hd), &(av[19].hd) }, 0 },
  361.  
  362.   { { 0, &(av[20].hd), &(av[20].hd) }, 0 },
  363.   { { 0, &(av[21].hd), &(av[21].hd) }, 0 },
  364.   { { 0, &(av[22].hd), &(av[22].hd) }, 0 },
  365.   { { 0, &(av[23].hd), &(av[23].hd) }, 0 },
  366.   { { 0, &(av[24].hd), &(av[24].hd) }, 0 },
  367.   { { 0, &(av[25].hd), &(av[25].hd) }, 0 },
  368.   { { 0, &(av[26].hd), &(av[26].hd) }, 0 },
  369.   { { 0, &(av[27].hd), &(av[27].hd) }, 0 },
  370.   { { 0, &(av[28].hd), &(av[28].hd) }, 0 },
  371.   { { 0, &(av[29].hd), &(av[29].hd) }, 0 },
  372.  
  373.   { { 0, &(av[30].hd), &(av[30].hd) }, 0 },
  374.   { { 0, &(av[31].hd), &(av[31].hd) }, 0 },
  375.   { { 0, &(av[32].hd), &(av[32].hd) }, 0 },
  376.   { { 0, &(av[33].hd), &(av[33].hd) }, 0 },
  377.   { { 0, &(av[34].hd), &(av[34].hd) }, 0 },
  378.   { { 0, &(av[35].hd), &(av[35].hd) }, 0 },
  379.   { { 0, &(av[36].hd), &(av[36].hd) }, 0 },
  380.   { { 0, &(av[37].hd), &(av[37].hd) }, 0 },
  381.   { { 0, &(av[38].hd), &(av[38].hd) }, 0 },
  382.   { { 0, &(av[39].hd), &(av[39].hd) }, 0 },
  383.  
  384.   { { 0, &(av[40].hd), &(av[40].hd) }, 0 },
  385.   { { 0, &(av[41].hd), &(av[41].hd) }, 0 },
  386.   { { 0, &(av[42].hd), &(av[42].hd) }, 0 },
  387.   { { 0, &(av[43].hd), &(av[43].hd) }, 0 },
  388.   { { 0, &(av[44].hd), &(av[44].hd) }, 0 },
  389.   { { 0, &(av[45].hd), &(av[45].hd) }, 0 },
  390.   { { 0, &(av[46].hd), &(av[46].hd) }, 0 },
  391.   { { 0, &(av[47].hd), &(av[47].hd) }, 0 },
  392.   { { 0, &(av[48].hd), &(av[48].hd) }, 0 },
  393.   { { 0, &(av[49].hd), &(av[49].hd) }, 0 },
  394.  
  395.   { { 0, &(av[50].hd), &(av[50].hd) }, 0 },
  396.   { { 0, &(av[51].hd), &(av[51].hd) }, 0 },
  397.   { { 0, &(av[52].hd), &(av[52].hd) }, 0 },
  398.   { { 0, &(av[53].hd), &(av[53].hd) }, 0 },
  399.   { { 0, &(av[54].hd), &(av[54].hd) }, 0 },
  400.   { { 0, &(av[55].hd), &(av[55].hd) }, 0 },
  401.   { { 0, &(av[56].hd), &(av[56].hd) }, 0 },
  402.   { { 0, &(av[57].hd), &(av[57].hd) }, 0 },
  403.   { { 0, &(av[58].hd), &(av[58].hd) }, 0 },
  404.   { { 0, &(av[59].hd), &(av[59].hd) }, 0 },
  405.  
  406.   { { 0, &(av[60].hd), &(av[60].hd) }, 0 },
  407.   { { 0, &(av[61].hd), &(av[61].hd) }, 0 },
  408.   { { 0, &(av[62].hd), &(av[62].hd) }, 0 },
  409.   { { 0, &(av[63].hd), &(av[63].hd) }, 0 },
  410.   { { 0, &(av[64].hd), &(av[64].hd) }, 0 },
  411.   { { 0, &(av[65].hd), &(av[65].hd) }, 0 },
  412.   { { 0, &(av[66].hd), &(av[66].hd) }, 0 },
  413.   { { 0, &(av[67].hd), &(av[67].hd) }, 0 },
  414.   { { 0, &(av[68].hd), &(av[68].hd) }, 0 },
  415.   { { 0, &(av[69].hd), &(av[69].hd) }, 0 },
  416.  
  417.   { { 0, &(av[70].hd), &(av[70].hd) }, 0 },
  418.   { { 0, &(av[71].hd), &(av[71].hd) }, 0 },
  419.   { { 0, &(av[72].hd), &(av[72].hd) }, 0 },
  420.   { { 0, &(av[73].hd), &(av[73].hd) }, 0 },
  421.   { { 0, &(av[74].hd), &(av[74].hd) }, 0 },
  422.   { { 0, &(av[75].hd), &(av[75].hd) }, 0 },
  423.   { { 0, &(av[76].hd), &(av[76].hd) }, 0 },
  424.   { { 0, &(av[77].hd), &(av[77].hd) }, 0 },
  425.   { { 0, &(av[78].hd), &(av[78].hd) }, 0 },
  426.   { { 0, &(av[79].hd), &(av[79].hd) }, 0 },
  427.  
  428.   { { 0, &(av[80].hd), &(av[80].hd) }, 0 },
  429.   { { 0, &(av[81].hd), &(av[81].hd) }, 0 },
  430.   { { 0, &(av[82].hd), &(av[82].hd) }, 0 },
  431.   { { 0, &(av[83].hd), &(av[83].hd) }, 0 },
  432.   { { 0, &(av[84].hd), &(av[84].hd) }, 0 },
  433.   { { 0, &(av[85].hd), &(av[85].hd) }, 0 },
  434.   { { 0, &(av[86].hd), &(av[86].hd) }, 0 },
  435.   { { 0, &(av[87].hd), &(av[87].hd) }, 0 },
  436.   { { 0, &(av[88].hd), &(av[88].hd) }, 0 },
  437.   { { 0, &(av[89].hd), &(av[89].hd) }, 0 },
  438.  
  439.   { { 0, &(av[90].hd), &(av[90].hd) }, 0 },
  440.   { { 0, &(av[91].hd), &(av[91].hd) }, 0 },
  441.   { { 0, &(av[92].hd), &(av[92].hd) }, 0 },
  442.   { { 0, &(av[93].hd), &(av[93].hd) }, 0 },
  443.   { { 0, &(av[94].hd), &(av[94].hd) }, 0 },
  444.   { { 0, &(av[95].hd), &(av[95].hd) }, 0 },
  445.   { { 0, &(av[96].hd), &(av[96].hd) }, 0 },
  446.   { { 0, &(av[97].hd), &(av[97].hd) }, 0 },
  447.   { { 0, &(av[98].hd), &(av[98].hd) }, 0 },
  448.   { { 0, &(av[99].hd), &(av[99].hd) }, 0 },
  449.  
  450.   { { 0, &(av[100].hd), &(av[100].hd) }, 0 },
  451.   { { 0, &(av[101].hd), &(av[101].hd) }, 0 },
  452.   { { 0, &(av[102].hd), &(av[102].hd) }, 0 },
  453.   { { 0, &(av[103].hd), &(av[103].hd) }, 0 },
  454.   { { 0, &(av[104].hd), &(av[104].hd) }, 0 },
  455.   { { 0, &(av[105].hd), &(av[105].hd) }, 0 },
  456.   { { 0, &(av[106].hd), &(av[106].hd) }, 0 },
  457.   { { 0, &(av[107].hd), &(av[107].hd) }, 0 },
  458.   { { 0, &(av[108].hd), &(av[108].hd) }, 0 },
  459.   { { 0, &(av[109].hd), &(av[109].hd) }, 0 },
  460.  
  461.   { { 0, &(av[110].hd), &(av[110].hd) }, 0 },
  462.   { { 0, &(av[111].hd), &(av[111].hd) }, 0 },
  463.   { { 0, &(av[112].hd), &(av[112].hd) }, 0 },
  464.   { { 0, &(av[113].hd), &(av[113].hd) }, 0 },
  465.   { { 0, &(av[114].hd), &(av[114].hd) }, 0 },
  466.   { { 0, &(av[115].hd), &(av[115].hd) }, 0 },
  467.   { { 0, &(av[116].hd), &(av[116].hd) }, 0 },
  468.   { { 0, &(av[117].hd), &(av[117].hd) }, 0 },
  469.   { { 0, &(av[118].hd), &(av[118].hd) }, 0 },
  470.   { { 0, &(av[119].hd), &(av[119].hd) }, 0 }
  471. };
  472.  
  473. #include "SpinLock.h"
  474. static SpinLockType avlock[MAXBIN] =
  475. {
  476.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  477.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  478.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  479.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  480.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  481.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  482.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  483.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  484.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  485.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  486.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  487.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  488.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  489.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  490.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  491.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  492.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  493.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  494.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  495.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  496.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  497.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  498.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree,
  499.   SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree, SpinLockFree
  500.   };
  501.  
  502.  
  503. /*
  504.   indexing into bins
  505. */
  506.  
  507. static inline mbinptr size2bin(unsigned int sz)
  508. {
  509.   mbinptr b = av;
  510.   while (sz >= (MINSIZE * 2)) { b += 4; sz >>= 1; } /* find power of 2 */
  511.   b += (sz - MINSIZE) >> 2;                         /* find quadrant */
  512.   return b;
  513. }
  514.  
  515.  
  516.  
  517. /* counts maintained if MALLOC_STATS defined */
  518.  
  519. #ifdef MALLOC_STATS
  520.  
  521. static unsigned int sbrked_mem;
  522. static unsigned int requested_mem;
  523. static unsigned int malloced_mem;
  524. static unsigned int freed_mem;
  525. static unsigned int max_used_mem;
  526.  
  527. static unsigned int n_sbrks;
  528. static unsigned int n_mallocs;
  529. static unsigned int n_frees;
  530. static unsigned int n_reallocs;
  531. static unsigned int n_reallocs_with_copy;
  532. static unsigned int n_avail;
  533. static unsigned int max_inuse;
  534.  
  535. static unsigned int n_malloc_chunks;
  536. static unsigned int n_malloc_bins;
  537.  
  538. static unsigned int n_split;
  539. static unsigned int n_consol;
  540.  
  541.  
  542. static void do_malloc_stats(const mchunkptr p)
  543. {
  544.   ++n_mallocs;
  545.   if ((n_mallocs-n_frees) > max_inuse)
  546.     max_inuse = n_mallocs - n_frees;
  547.   malloced_mem += (p->size & ~(INUSE));
  548.   if (malloced_mem - freed_mem > max_used_mem)
  549.     max_used_mem = malloced_mem - freed_mem;
  550. }
  551.  
  552. static void do_free_stats(const mchunkptr p)
  553. {
  554.   ++n_frees;
  555.   freed_mem += (p->size & ~(INUSE));
  556. }        
  557.  
  558. #endif
  559.  
  560.  
  561.  
  562. /* Utilities needed below for memalign */
  563. /* This is redundant with libg++ support, but not if used stand-alone */
  564.  
  565. static unsigned int gcd(unsigned int a, unsigned int b)
  566. {
  567.   unsigned int tmp;
  568.   
  569.   if (b > a)
  570.   {
  571.     tmp = a; a = b; b = tmp;
  572.   }
  573.   for(;;)
  574.   {
  575.     if (b == 0)
  576.       return a;
  577.     else if (b == 1)
  578.       return b;
  579.     else
  580.     {
  581.       tmp = b;
  582.       b = a % b;
  583.       a = tmp;
  584.     }
  585.   }
  586. }
  587.  
  588. static inline unsigned int lcm(unsigned int x, unsigned int y)
  589. {
  590.   return x / gcd(x, y) * y;
  591. }
  592.  
  593.  
  594.  
  595. /* maintaining INUSE via size field */
  596.  
  597.  
  598. #define inuse(p)       ((p)->size & INUSE)
  599. #define set_inuse(p)   ((p)->size |= INUSE)
  600. #define clear_inuse(b) ((p)->size &= ~INUSE)
  601.  
  602.   
  603. /* operations on  malloc_chunk addresses */
  604.  
  605.  
  606. /* return ptr to next physical malloc_chunk */
  607.  
  608. #define next_chunk(p) ((mchunkptr)((char*)(p) + (p)->size))
  609.  
  610. /* return ptr to previous physical malloc_chunk */
  611.  
  612. #define prev_chunk(p) ((mchunkptr)((char*)(p)-((((int*)(p))[-1]) & ~(INUSE))))
  613.  
  614. /* place size at front and back of chunk */
  615.  
  616.  
  617. static inline void set_size(mchunkptr p, unsigned int sz)
  618. {
  619.   p->size = *((int*)((char*)(p) + sz - SIZE_SZ)) = sz;
  620. }
  621.  
  622.  
  623.  
  624.  
  625. /* conversion from malloc headers to user pointers, and back */
  626.  
  627. static inline void* chunk2mem(mchunkptr p) 
  628.   set_inuse(p);
  629.   return (void*)((char*)(p) + SIZE_SZ); 
  630. }
  631.  
  632. static inline mchunkptr mem2chunk(void* mem) 
  633.   mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ); 
  634.  
  635.   /* a quick sanity check */
  636.   unsigned int sz = p->size & ~(INUSE);
  637.   if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
  638.     malloc_user_error();
  639.  
  640.   p->size = sz;   /* clears INUSE */
  641.   return p;
  642. }
  643.  
  644.  
  645.  
  646. /* maintaining bins & pointers */
  647.  
  648.  
  649. /* maximum bin actually used */
  650.  
  651. static mbinptr malloc_maxbin = FIRSTBIN;
  652.  
  653.  
  654. /* The designated victim bin. */
  655.  
  656. static mbinptr malloc_victim = FIRSTBIN;
  657.  
  658.  
  659.  
  660.  
  661. /* operations on lists inside bins */
  662.  
  663.  
  664. /* take a chunk off a list */
  665.  
  666. static inline void unlink(mchunkptr p)
  667. {
  668.   mchunkptr b = p->bk;
  669.   mchunkptr f = p->fd;
  670.  
  671.   f->bk = b;  b->fd = f;
  672.  
  673.   UPDATE_STATS (--n_avail);
  674. }
  675.  
  676.  
  677.  
  678. /* split a chunk and place on the back of a list */
  679.  
  680. static inline void split(mchunkptr p, unsigned int offset)
  681. {
  682.   unsigned int room = p->size - offset;
  683.   if (room >= MINSIZE)
  684.   {
  685.     mbinptr   bn = size2bin(room);                  /* new bin */
  686.     mchunkptr h  = &(bn->hd);                       /* its head */
  687.     mchunkptr b  = h->bk;                           /* old back element */
  688.     mchunkptr t = (mchunkptr)((char*)(p) + offset); /* remaindered chunk */
  689.     
  690.     /* set size */
  691.     t->size = *((int*)((char*)(t) + room    - SIZE_SZ)) = room;
  692.  
  693.     /* link up */
  694.     t->bk = b;  t->fd = h;  h->bk = b->fd = t;
  695.     
  696.     /* adjust maxbin (h == b means was empty) */
  697.     if (h == b && bn > malloc_maxbin) malloc_maxbin = bn; 
  698.  
  699.     /* use as next victim */
  700.     malloc_victim = bn;
  701.     
  702.     /* adjust size of chunk to be returned */
  703.     p->size = *((int*)((char*)(p) + offset  - SIZE_SZ)) = offset;
  704.  
  705.     UPDATE_STATS ((++n_split, ++n_avail));
  706.   }
  707. }
  708.  
  709.  
  710.  
  711. /* place a consolidated chunk on the back of a list */
  712. /* like above, except no split */
  713.  
  714. static inline void consollink(mchunkptr p)
  715. {
  716.   mbinptr   bn = size2bin(p->size);
  717.   mchunkptr h  = &(bn->hd);
  718.   mchunkptr b  = h->bk;
  719.  
  720.   p->bk = b;  p->fd = h;  h->bk = b->fd = p;
  721.  
  722.   if (h == b && bn > malloc_maxbin) malloc_maxbin = bn; 
  723.  
  724.   malloc_victim = bn;        /* use as next victim */
  725.  
  726.   UPDATE_STATS(++n_avail);
  727. }
  728.  
  729.  
  730. /* place a freed chunk on the front of a list */
  731.  
  732. static inline void frontlink(mchunkptr p)
  733. {
  734.   mbinptr   bn = size2bin(p->size);
  735.   mchunkptr h  = &(bn->hd);
  736.   mchunkptr f  = h->fd;
  737.  
  738.   p->bk = h;  p->fd = f;  f->bk = h->fd = p;
  739.  
  740.   if (h == f && bn > malloc_maxbin) malloc_maxbin = bn;  
  741.  
  742.   bn->dirty = 1;
  743.  
  744.   UPDATE_STATS(++n_avail);
  745. }
  746.  
  747.  
  748.  
  749. /* Dealing with sbrk */
  750.  
  751.  
  752. /* To link consecutive sbrk regions when possible */
  753.  
  754. static int* last_sbrk_end;
  755.  
  756.  
  757. /*  who to call when sbrk returns failure */
  758.  
  759. #ifndef NO_NEW_HANDLER
  760. typedef volatile void (*vfp)();
  761. #ifdef __cplusplus
  762. extern "C" vfp __new_handler;
  763. #else
  764. extern vfp __new_handler;
  765. #endif
  766. #endif
  767.  
  768. static mchunkptr malloc_from_sys(unsigned nb)
  769. {
  770.   mchunkptr p;
  771.   unsigned int sbrk_size;
  772.   int* ip;
  773.   
  774.   /* Minimally, we need to pad with enough space */
  775.   /* to place dummy size/use fields to ends if needed */
  776.  
  777.   sbrk_size = ((nb + SBRK_UNIT - 1 + SIZE_SZ + SIZE_SZ) 
  778.                / SBRK_UNIT) * SBRK_UNIT;
  779.  
  780.   ip = (int*)(sbrk(sbrk_size));
  781.   if ((char*)ip == (char*)(-1)) /* sbrk returns -1 on failure */
  782.   {
  783. #ifndef NO_NEW_HANDLER
  784.     (*__new_handler) ();
  785. #endif
  786.     return 0;
  787.   }
  788.  
  789.   UPDATE_STATS ((++n_sbrks, sbrked_mem += sbrk_size));
  790.  
  791.  
  792.   if (last_sbrk_end != &ip[-1]) 
  793.   {                             
  794.     /* It's either first time through or someone else called sbrk. */
  795.     /* Arrange end-markers at front & back */
  796.  
  797.     /* Shouldn't be necessary, but better to be safe */
  798.     while (!aligned_OK(ip)) { ++ip; sbrk_size -= SIZE_SZ; }
  799.  
  800.  
  801.     /* Mark the front as in use to prevent merging. */
  802.     /* Note we can get away with only 1 word, not MINSIZE overhead here */
  803.  
  804.     *ip++ = SIZE_SZ | INUSE;
  805.     
  806.     p = (mchunkptr)ip;
  807.     set_size(p,sbrk_size - (SIZE_SZ + SIZE_SZ)); 
  808.     
  809.   }
  810.   else 
  811.   {
  812.     mchunkptr l;  
  813.  
  814.     /* We can safely make the header start at end of prev sbrked chunk. */
  815.     /* We will still have space left at the end from a previous call */
  816.     /* to place the end marker, below */
  817.  
  818.     p = (mchunkptr)(last_sbrk_end);
  819.     set_size(p, sbrk_size);
  820.  
  821.  
  822.     /* Even better, maybe we can merge with last fragment: */
  823.  
  824.     l = prev_chunk(p);
  825.     if (!inuse(l))  
  826.     {
  827.       unlink(l);
  828.       set_size(l, p->size + l->size);
  829.       p = l;
  830.     }
  831.  
  832.   }
  833.  
  834.   /* mark the end of sbrked space as in use to prevent merging */
  835.  
  836.   last_sbrk_end = (int*)((char*)p + p->size);
  837.   *last_sbrk_end = SIZE_SZ | INUSE;
  838.  
  839.   UPDATE_STATS((++n_avail, ++n_malloc_chunks));
  840.   
  841.   return p;
  842. }
  843.  
  844.  
  845.  
  846. /* Consolidate dirty bins. */
  847. /* Stop if found a chunk big enough to satisfy current malloc request */
  848.  
  849. /* (It requires much less bookkeeping to consolidate entire bins */
  850. /* at once than to keep records of which chunks might be */
  851. /* consolidatable. So long as the lists are short, which we */
  852. /* try to ensure via small bin ranges, there is little wasted effort.) */
  853.  
  854. static mchunkptr malloc_find_space(unsigned int nb)
  855. {
  856.   mbinptr b;
  857.   mchunkptr usable = 0;
  858.  
  859.   /* first, re-adjust max used bin */
  860.  
  861.   while (malloc_maxbin >= FIRSTBIN && 
  862.          malloc_maxbin->hd.bk == &(malloc_maxbin->hd))
  863.   {
  864.     malloc_maxbin->dirty = 0;
  865.     --malloc_maxbin;
  866.   }
  867.  
  868.   for (b = malloc_maxbin; b >= FIRSTBIN; --b)
  869.   {
  870.     UPDATE_STATS(++n_malloc_bins);
  871.  
  872.     if (b->dirty)
  873.     {
  874.       mchunkptr h = &(b->hd);         /* head of list */
  875.       mchunkptr p = h->bk;            /* chunk traverser */
  876.  
  877.       while (p != h)
  878.       {
  879.         mchunkptr nextp = p->bk;       /* save, in case of relinks */
  880.         int consolidated = 0;          /* only unlink/relink if consolidated */
  881.  
  882.         mchunkptr t;
  883.         while (!inuse(t = prev_chunk(p))) /* consolidate backward */
  884.         {
  885.           if (!consolidated) { consolidated = 1; unlink(p); }
  886.           if (t == nextp) nextp = t->bk;
  887.           unlink(t);
  888.           set_size(t, t->size + p->size);
  889.           p = t;
  890.           UPDATE_STATS (++n_consol);
  891.         }
  892.         
  893.         while (!inuse(t = next_chunk(p))) /* consolidate forward */
  894.         {
  895.           if (!consolidated) { consolidated = 1; unlink(p); }
  896.           if (t == nextp) nextp = t->bk;
  897.           unlink(t);
  898.           set_size(p, p->size + t->size);
  899.           UPDATE_STATS (++n_consol);
  900.         }
  901.  
  902.         if (consolidated)
  903.         {
  904.           consollink(p);
  905.           if (p->size >= nb)
  906.             usable = p;
  907.         }
  908.  
  909.         UPDATE_STATS(++n_malloc_chunks);
  910.         p = nextp;
  911.  
  912.       }
  913.  
  914.       b->dirty = 0;
  915.  
  916.       if (usable != 0) 
  917.       {
  918.         unlink(usable);
  919.         return usable;
  920.       }
  921.  
  922.     }
  923.   }
  924.  
  925.   /* nothing available - sbrk some more */
  926.  
  927.   return malloc_from_sys(nb);
  928. }
  929.  
  930.  
  931.  
  932. /*   Finally, the user-level functions  */
  933.  
  934. void* malloc(unsigned int bytes)
  935. {
  936.   unsigned int nb  = request2size(bytes);  /* padded request size */
  937.   mbinptr      b   = size2bin(nb);         /* corresponding bin */
  938.   mchunkptr    hd  = &(b->hd);             /* head of its list */
  939.   mchunkptr    p;                          /* chunk traverser */
  940.  
  941.   UPDATE_STATS((requested_mem+=bytes, ++n_malloc_bins));
  942.  
  943.   /* Try a (near) exact match in own bin */
  944.  
  945.   for (p = hd->fd; p != hd; p = p->fd)
  946.   {
  947.     UPDATE_STATS(++n_malloc_chunks);
  948.  
  949.     if (p->size >= nb)
  950.     {
  951.       unlink(p);
  952.       goto found;
  953.     }
  954.   }
  955.  
  956.   /* No exact match, so select a victim */
  957.  
  958.   UPDATE_STATS(++n_malloc_chunks);
  959.  
  960.   p = malloc_victim->hd.bk; 
  961.   if (p->size >= nb)
  962.     unlink(p);
  963.   else
  964.   {
  965.     /* Find a new victim. */
  966.  
  967.     for (;;)
  968.     {
  969.       UPDATE_STATS(++n_malloc_bins);
  970.       ++b;
  971.       p = b->hd.bk;
  972.       if (p != &(b->hd)) 
  973.       {
  974.         /* p must be usable since it's in bigger bin */
  975.         /* Consolidate, so it can serve as a victim longer */
  976.  
  977.         mchunkptr t;
  978.  
  979.         unlink(p);
  980.  
  981.         while (!inuse(t = prev_chunk(p))) /* consolidate backward */
  982.         {
  983.           unlink(t);
  984.           set_size(t, t->size + p->size);
  985.           p = t;
  986.           UPDATE_STATS (++n_consol);
  987.         }
  988.         
  989.         while (!inuse(t = next_chunk(p))) /* consolidate forward */
  990.         {
  991.           unlink(t);
  992.           set_size(p, p->size + t->size);
  993.           UPDATE_STATS (++n_consol);
  994.         }
  995.  
  996.         malloc_victim = b;  /* record this bin for next time */
  997.         break;
  998.       }
  999.       else if (b > malloc_maxbin)
  1000.       {
  1001.         p = malloc_find_space(nb);
  1002.         if (p == 0)
  1003.           return 0;
  1004.         else
  1005.           break;
  1006.       }
  1007.     }
  1008.   }
  1009.  
  1010.   /* use what we found */
  1011.  
  1012.  found:
  1013.  
  1014.   split(p, nb); 
  1015.   UPDATE_STATS(do_malloc_stats(p));
  1016.   return chunk2mem(p);
  1017. }
  1018.  
  1019.  
  1020.  
  1021.  
  1022. void free(void* mem)
  1023. {
  1024.   if (mem != 0)
  1025.   {
  1026.     mchunkptr p = mem2chunk(mem);
  1027.     UPDATE_STATS(do_free_stats(p));
  1028.     frontlink(p);
  1029.   }
  1030. }
  1031.  
  1032.  
  1033. void* calloc(unsigned int n, unsigned int elem_size)
  1034. {
  1035.   unsigned int sz = n * elem_size;
  1036.   void* p = malloc(sz);
  1037.   bzero(p, sz);
  1038.   return p;
  1039. };
  1040.  
  1041. /* This is here for compatibility with older systems */
  1042. void cfree(void *mem)
  1043. {
  1044.   free(mem);
  1045. }
  1046.  
  1047.  
  1048. unsigned int malloc_usable_size(void* mem)
  1049. {
  1050.   if (mem == 0)
  1051.     return 0;
  1052.   else
  1053.   {
  1054.     mchunkptr p = (mchunkptr)((char*)(mem) - SIZE_SZ); 
  1055.     unsigned int sz = p->size & ~(INUSE);
  1056.     if (p->size == sz || sz != *((int*)((char*)(p) + sz - SIZE_SZ)))
  1057.       return 0;
  1058.     else
  1059.       return sz - MALLOC_MIN_OVERHEAD;
  1060.   }
  1061. }
  1062.  
  1063.  
  1064.  
  1065. void* realloc(void* mem, unsigned int bytes)
  1066. {
  1067.   if (mem == 0) 
  1068.     return malloc(bytes);
  1069.   else
  1070.   {
  1071.     unsigned int nb      = request2size(bytes);
  1072.     mchunkptr    p       = mem2chunk(mem);
  1073.     unsigned int oldsize = p->size;
  1074.     int          room;
  1075.     mchunkptr    nxt;
  1076.  
  1077.     UPDATE_STATS((++n_reallocs, requested_mem += bytes-oldsize));
  1078.     
  1079.     /* try to expand (even if already big enough), to clean up chunk */
  1080.  
  1081.     while (!inuse(nxt = next_chunk(p)))
  1082.     {
  1083.       UPDATE_STATS ((malloced_mem += nxt->size, ++n_consol));
  1084.       unlink(nxt);
  1085.       set_size(p, p->size + nxt->size);
  1086.     }
  1087.  
  1088.     room = p->size - nb;
  1089.     if (room >= 0)
  1090.     {
  1091.       if (room >= MINSIZE)
  1092.       {
  1093.         split(p, nb);
  1094.         UPDATE_STATS(malloced_mem -= room);
  1095.       }
  1096.       
  1097.       return chunk2mem(p);
  1098.     }
  1099.     else /* do the obvious */
  1100.     {
  1101.       void* newmem;
  1102.       set_inuse(p);    /* don't let malloc consolidate us yet! */
  1103.       newmem = malloc(nb);
  1104.       bcopy(mem, newmem, oldsize - SIZE_SZ);
  1105.       free(mem);
  1106.       UPDATE_STATS(++n_reallocs_with_copy);
  1107.       return newmem;
  1108.     }
  1109.   }
  1110. }
  1111.  
  1112.  
  1113.  
  1114. /* return a pointer to space with at least the alignment requested */
  1115.  
  1116. void* memalign(unsigned int alignment, unsigned int bytes)
  1117. {
  1118.   mchunkptr p;
  1119.   unsigned int nb = request2size(bytes);
  1120.  
  1121.   /* find an alignment that both we and the user can live with: */
  1122.   /* least common multiple guarantees mutual happiness */
  1123.   unsigned int align = lcm(alignment, MALLOC_MIN_OVERHEAD);
  1124.   unsigned int mask = align - 1;
  1125.  
  1126.   /* call malloc with worst case padding to hit alignment; */
  1127.   /* we will give back extra */
  1128.  
  1129.   unsigned int req = nb + align + MINSIZE;
  1130.   void* m = malloc(req);
  1131.  
  1132.   if (m == 0) return m;
  1133.  
  1134.   p = mem2chunk(m);
  1135.  
  1136.   /* keep statistics on track */
  1137.  
  1138.   UPDATE_STATS(--n_mallocs);
  1139.   UPDATE_STATS(malloced_mem -= p->size);
  1140.   UPDATE_STATS(requested_mem -= req);
  1141.   UPDATE_STATS(requested_mem += bytes);
  1142.  
  1143.   if (((int)(m) & (mask)) != 0) /* misaligned */
  1144.   {
  1145.  
  1146.     /* find an aligned spot inside chunk */
  1147.  
  1148.     mchunkptr ap = (mchunkptr)(( ((int)(m) + mask) & -align) - SIZE_SZ);
  1149.  
  1150.     unsigned int gap = (unsigned int)(ap) - (unsigned int)(p);
  1151.     unsigned int room;
  1152.  
  1153.     /* we need to give back leading space in a chunk of at least MINSIZE */
  1154.  
  1155.     if (gap < MINSIZE)
  1156.     {
  1157.       /* This works since align >= MINSIZE */
  1158.       /* and we've malloc'd enough total room */
  1159.  
  1160.       ap = (mchunkptr)( (int)(ap) + align );
  1161.       gap += align;    
  1162.     }
  1163.  
  1164.     if (gap + nb > p->size) /* can't happen unless chunk sizes corrupted */
  1165.       malloc_user_error();
  1166.  
  1167.     room = p->size - gap;
  1168.  
  1169.     /* give back leader */
  1170.     set_size(p, gap);
  1171.     consollink(p);
  1172.  
  1173.     /* use the rest */
  1174.     p = ap;
  1175.     set_size(p, room);
  1176.   }
  1177.  
  1178.   /* also give back spare room at the end */
  1179.  
  1180.   split(p, nb); 
  1181.   UPDATE_STATS(do_malloc_stats(p));
  1182.   return chunk2mem(p);
  1183.  
  1184. }
  1185.  
  1186. #if !defined(sun) && !defined(ultrix)
  1187. #  include <getpagesize.h>
  1188. #endif
  1189.  
  1190. static int pagesize = 0;
  1191.  
  1192. void* valloc(unsigned int bytes)
  1193. {
  1194.   if ( pagesize == 0 ) pagesize = getpagesize();
  1195.   return memalign (pagesize, bytes);
  1196. }
  1197.     
  1198.  
  1199. void malloc_stats()
  1200. {
  1201. #ifndef MALLOC_STATS
  1202. }
  1203. #else
  1204.   int i;
  1205.   mchunkptr p;
  1206.   double nm = (double)(n_mallocs + n_reallocs);
  1207.  
  1208.   fprintf(stderr, "\nmalloc statistics\n\n");
  1209.  
  1210.   if (n_mallocs != 0)
  1211.   fprintf(stderr, "requests  = %10u total size = %10u\tave = %10u\n",
  1212.           n_mallocs, requested_mem, requested_mem/n_mallocs);
  1213.  
  1214.   if (n_mallocs != 0)
  1215.   fprintf(stderr, "mallocs   = %10u total size = %10u\tave = %10u\n",
  1216.           n_mallocs, malloced_mem, malloced_mem/n_mallocs);
  1217.   
  1218.   if (n_frees != 0)
  1219.   fprintf(stderr, "frees     = %10u total size = %10u\tave = %10u\n",
  1220.           n_frees, freed_mem, freed_mem/n_frees);
  1221.   
  1222.   if (n_mallocs-n_frees != 0)
  1223.   fprintf(stderr, "in use    = %10u total size = %10u\tave = %10u\n",
  1224.           n_mallocs-n_frees, malloced_mem-freed_mem, 
  1225.           (malloced_mem-freed_mem) / (n_mallocs-n_frees));
  1226.  
  1227.   if (max_inuse != 0)
  1228.   fprintf(stderr, "max in use= %10u total size = %10u\tave = %10u\n",
  1229.           max_inuse, max_used_mem, max_used_mem / max_inuse);
  1230.   
  1231.   if (n_avail != 0)
  1232.   fprintf(stderr, "available = %10u total size = %10u\tave = %10u\n",
  1233.           n_avail, sbrked_mem - (malloced_mem-freed_mem), 
  1234.           (sbrked_mem - (malloced_mem-freed_mem)) / n_avail);
  1235.  
  1236.   if (n_sbrks != 0)
  1237.   fprintf(stderr, "sbrks     = %10u total size = %10u\tave = %10u\n\n",
  1238.           n_sbrks, sbrked_mem, sbrked_mem/ n_sbrks);
  1239.  
  1240.   if (n_reallocs != 0)
  1241.   fprintf(stderr, "reallocs  = %10u with copy  = %10u\n\n",
  1242.           n_reallocs, n_reallocs_with_copy);
  1243.  
  1244.  
  1245.   if (nm != 0)
  1246.   {
  1247.     fprintf(stderr, "chunks scanned per malloc = %6.3f\n", 
  1248.             n_malloc_chunks / nm);
  1249.     fprintf(stderr, "bins scanned per malloc   = %6.3f\n", 
  1250.             n_malloc_bins / nm);
  1251.     fprintf(stderr, "splits per malloc         = %6.3f\n", 
  1252.             n_split / nm);
  1253.     fprintf(stderr, "consolidations per malloc = %6.3f\n", 
  1254.             n_consol / nm);
  1255.   }
  1256.  
  1257.   fprintf(stderr, "\nfree chunks:\n");
  1258.   for (i = 0; i < MAXBIN; ++i)
  1259.   {
  1260.     p = av[i].hd.fd;
  1261.     if (p != &(av[i].hd))
  1262.     {
  1263.       unsigned int count = 1;
  1264.       unsigned int sz = p->size;
  1265.       for (p = p->fd; p != &(av[i].hd); p = p->fd)
  1266.       {
  1267.         if (p->size == sz)
  1268.           ++count;
  1269.         else
  1270.         {
  1271.           fprintf(stderr, "\tsize = %10u count = %5u\n", sz, count);
  1272.           count = 1;
  1273.           sz = p->size;
  1274.         }
  1275.       }
  1276.  
  1277.       fprintf(stderr, "\tsize = %10u count = %5u\n", sz, count);
  1278.  
  1279.     }
  1280.   }
  1281. }
  1282. #endif /* MALLOC_STATS */
  1283.  
  1284. #endif /* NO_LIBGXX_MALLOC */
  1285.